Since its inception, the internet has grown at a rapid rate, typically at least doubling in size each year. This rapid growth continually brings to light new problems and limitations associated with changes in the manner and scale of communication.
The global Internet is a loose coalition of independently operated but interconnected constituent networks, known as autonomous systems (AS). Each autonomous system is responsible for its own customers, provision of services, pricing, and policies, but shares with other autonomous systems a common view of addressing and routing. In particular, routing between autonomous systems, by exchange of network level reachability information (NLRI, encoded as address prefixes), is established and maintained by means of a border gateway protocol (BGP).
BGP is the Internet's Network-Network Interface (NNI), and is the tool available to implement the commercial agreements between IP Service Providers. In general, every border router at the edge of an AS runs BGP:                external BGP sessions are maintained between each pair of directly connected border routers in adjacent AS's (external peers)        internal BGP sessions are maintained between all border routers belonging to the same AS; this logical full-mesh requirement is often implemented via Route Reflector(s)        
At such peering points, the offer of routes is used to control the flow of traffic.
The essence of BGP operation can be captured by describing the behaviour following receipt of an update by a border router on a given AS, my_AS, from AS1234. This will have the form:    UPDATE(ASpath=<AS1234, AS5678>, NLRI={list of IP prefixes})(this ignores volumes of other parameters)
This means that the IP address space defined by the list of IP prefixes is reachable by the path defined, namely ASpath.
The receiving border router in my_AS then decides whether it can and will use this route:                the route is discarded if there is a loop, determined by seeing my_AS's number in the path        the route is discarded if disallowed by policy (eg I have a commercial agreement that traffic to AS5678 goes by another administration, not AS1234)        the route is not used if there is already a better route to those prefixes from my_AS        
A BGP speaker never propagates a route that it does not use itself.
Having decided to use an announced route, the receiving BGP speaker then:                1. installs the next hop (its external BGP peer) for that route in its own forwarding tables,        2. sends Updates to all its internal BGP peers (i.e. propagates the knowledge across its AS)        3. causes the route to be installed on all internal (non-border) routers within the AS, so that packets from anywhere within the AS will be routed to the correct border router. There are two ways:                    injection of the prefixes as a special external link advertisement into the IGP (e.g. OSPF), or            arranging that all routers in the backbone area are internal BGP speakers (even if they have no external connectivity), whereupon each can compute (using the IGP) the next hop towards the border router advertising a specific external route.                        
BGP speakers receiving a route from one of their internal peers in the same AS (step 2. above) must then decide whether to propagate this route to any of their external peers in adjacent AS's. Policy is again applied to make this decision (e.g. does my AS offer transit to my peer AS for traffic routed via AS1234?); if it is appropriate to advertise the route, the border router pre-pends its own AS number to the AS path (and modifies other parameters), and sends to each appropriate external peer an Update of the form:    UPDATE(ASpath=<my_AS, AS1234, AS5678>, NLRI={list of IP prefixes}).
Whilst a Border Gateway Protocol such as that described above provides an effective means of identifying routes between AS's, it suffers from the problem that under failure conditions, for example upon failure of any link between AS's or any border router which lies on a selected route, the route is withdrawn completely. Each AS previously having selected routes making use of the failed AS must then attempt to re-establish a new route from scratch, thereby causing significant routing traffic and loss of connectivity while alternative possible routes are determined. Furthermore, this effort to re-establish a route is required whether withdrawal of the failed AS is temporary (for example as a result of a system crash on that AS's nodes) or permanent (for example, the AS retires the node).
Historically, routing in the internet was hierachical. A small number (initially 1) of providers offered transit to local networks, and internet traffic was routed, by default, “upwards” in a local (e.g. national) hierarchy before being directed “across” to a relevant top-level gateway for onward transmission “downwards” to the ultimate recipient within that domain. Peering between local networks was rare.
Advent of commercial services and competition resulted in a proliferation of IP SPs, and an increasingly meshed network topology as commercial considerations lead to a massive increase in routing effected on a peer-to-peer basis between AS's. This, in turn, led to increasing size and complexity of the AS's local routing tables. This initial growth in routing table size was controlled by improved prefix aggregation permitted by Classless Interdomain Routing (CIDR), but has now resumed. The current growth of such “default-free” routing is once again stressing the capabilities of the Internet's BGP-4 protocol. (“Analyzing the Internet BGP Routing Table”, Geoff Huston, 2001). This growth appears to have two major sources:                increased peering between Autonomous Systems, probably as a result of the falling cost of transport bandwidth compared with IP transit,        an increase in the practice of end customers multi-homing onto multiple service providers (for resilience, cost and other reasons).        
The net effect of this is that the largely hierarchical structure of the Internet, on which Classless Interdomain Routing (CIDR) was predicated, is evolving to a much more richly connected mesh. The address aggregation which CIDR was intended to allow is consequently undermined by prefixes being reachable from multiple (topologically distant) places.
Furthermore it has been observed that BGP is increasingly being used for traffic engineering, with “more specific” prefixes (typically defining subsets of a service provider's address allocation) being used to control the gateway at which an upstream provider is directed to inject traffic onto the service provider's network.
This might not be a major concern if the effect were limited to Internet Protocol Version 4 (IPv4) only; however, it now seems likely to be an issue with Internet Protocol Version 6 (IPv6) into the future. IPv6 originally envisaged an address allocation scheme supporting aggregation even more aggressive than CIDR, with a hierarchy of service providers each inheriting address allocations from their upstream provider (Provider Addressing). If an AS multi-homed, it would inherit an allocation from each upstream provider, and all hosts and routers were required to handle the resultant multiple addresses. Protocol support was provided to minimise (but could not eliminate) the pain of renumbering events when any AS in the food chain (below the top level) altered its connectivity to other AS's.
However, it seems very likely that this hierarchical provider addressing model will never be adopted by the service provider community itself, even if it is required by them of end customers. The reasons for this include the fact that, with the increase in meshed connectivity, it becomes difficult to define what constitutes a “default-free” service provider.
Consequently, it seems likely that IPv6 Service Providers will all obtain their address allocations from Registries, with likely minimal correlation between allocation and Internet topology. As a result it is to be expected that IPv6 routing table growth will follow the same pattern as IPv4 except in a much larger space.
It is not believed that the size of the routing table per se is the major problem. In the control plane, memory size is not a practical limitation, and it is believed that the growth in size of the forwarding table can be accommodated with modern longest match algorithms.
However, significant problems with the current scheme include:                the number of iterations (hence time) which can be taken by BGP-4 (in essence using a distance vector algorithm) to identify a new route following a failure resulting in withdrawal of the original choice, and        the processing load resulting from the volume of Update messages which can be received in a short period (as a consequence of multiple instances of the above).        
Both of these problems are caused at root by a “flat” routing architecture, with little route abstraction possible (because the address allocation made has minimal correlation with the inter-AS network topology); this not only has an adverse impact on the number of routing table entries, but also on their dynamics, because any failure causing a route to be withdrawn is seen across the entire network, and does not have its visibility limited by existing forms of aggregation.
Furthermore, there does seem to be a fundamental constraint on the solution space. Modern Link State routing technology is able to minimise the messaging required to communicate changes in network state (by use of a “node and link” abstraction, rather than explicit routes), and recent work shows that fast “convergence” can be achieved for large networks. The price paid for this, as pointed out in “Analyzing the Internet Routing Table”, is Policy transparency across the entire network.
However, inter-domain Routing Policy is the only mechanism available to service providers to implement the commercial agreements they have made, and their overall business objectives, and some elements of these policies can be regarded as commercially sensitive. Therefore only those routing mechanisms supporting Policy opacity are likely to be commercially acceptable, and in practice this means using derivatives of BGP or similar protocol.